package com.LeeCode;

/**
 * 活字印刷
 */

public class Code1079 {
    public static void main(String[] args) {
        String tiles = "aaaBBC";
        System.out.println(new Code1079().numTilePossibilities(tiles));
    }

    private int[] pre = new int[7];
    private int ans = 0;

    public int numTilePossibilities(String tiles) {
        char[] chars = tiles.toCharArray();
        // 预处理前一个相同元素出现位置的数组
        for (int i = 0; i < chars.length; i++) {
            pre[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (chars[j] == chars[i]) {
                    pre[i] = j;
                    break;
                }
            }
        }

        backtrace(0, new boolean[chars.length]);

        return ans;
    }

    private void backtrace(int index, boolean[] visited) {
        if (index > 0) ans++; // 记录非空的可行答案

        if (index == visited.length) {
            return;
        }

        for (int i = 0; i < visited.length; i++) {
            /**
             * 选取可能元素
             * 1. 第一次出现且未被访问
             * 2. 未被访问过且前一个相同元素已经被访问过
             */
            if (!visited[i] && (pre[i] == -1 || visited[pre[i]])) {
                visited[i] = true;
                backtrace(index + 1, visited);
                visited[i] = false;
            }
        }
    }
}
